1. Field of the Invention
The present invention relates generally to unmanned aerial vehicles (UAVs), and in particular, to a method, system, apparatus, and article of manufacture for avoiding obstacles at high speeds using an arbitrary suite of range sensors.
2. Description of the Related Art
(Note: This application references a number of different publications as indicated throughout the specification by reference names and year enclosed in brackets, e.g., [Name 20xx]. A list of these different publications ordered according to these reference names and year can be found below in the section entitled “References.” Each of these publications is incorporated by reference herein.)
Micro air vehicles (MAVs) are a challenging UAV platform for high-speed autonomous flight in cluttered environments because their power and size restrictions severely limit the sensing and computational resources that can be carried onboard. As a result, obstacle detection and representation, trajectory generation, and motion planning must be performed in a highly compact and efficient fashion.
Vision-based obstacle detection has emerged as a popular way of satisfying constraints on sensing, primarily because cameras have low power requirements and are light enough to carry on even the smallest MAVs. Binocular stereo vision has been successfully used for forward-looking obstacle detection, and can be used to populate an occupancy grid world model that is useful for mapping and slow navigation missions [Fraundorfer 2012]. A second stereo vision-based approach that has received recent attention [Matthies 2014] avoids populating a voxel map and uses the disparity image format, as is acquired natively by the stereo pair, to directly and equivalently represent configuration space (C-space). Obstacles are artificially expanded by the vehicle dimensions directly in the disparity image coordinates, which admits fast collision-checking of trajectories as well as a simple and lightweight reactive motion planning algorithm. The disparity space representation has been generalized to an “egocylinder” by [Brockers1 2016], which offers a 360° field of regard as well as straightforward fusion of range data from stereo and monocular sensors into a single compact structure [Brockers2 2016].
Dynamical trajectory generation for MAVs typically relies on vehicle plant models with the differential flatness property, in which all vehicle states and controls can be expressed algebraically in terms of a smaller set of “flat outputs” [Murray 1995]. The class of differentially flat vehicles includes quadcopters as well as common car and fixed-wing aircraft abstractions, and is advantageous because trajectory generation for differentially flat vehicles does not require integration of the state equations. For quadcopters, differential flatness has been used to generate real-time “minimum snap” trajectories that penalize the fourth derivative of position to intentionally limit control input aggression [Mellinger 2011]. A minimum snap framework formed the basis of a trajectory generation scheme for obstacle avoidance over known maps in [Richter 2013]. When a vehicle is differentially flat in its configuration variables, a property known as configuration flatness, motion planning is further simplified because controls and state variables follow immediately from the vehicle's position relative to obstacles in C-space [Rathinam 1996]. The typical differentially flat point-mass MAV models receive such heavy use for obstacle avoidance because they are also configuration flat—a specialization that allows most of the control inputs and state variables to be entirely abstracted away from a navigation task. The quadcopter plant model of [Powers 2015], for example, is configuration flat in position once a yaw angle trajectory (which can be chosen independently of the obstacle layout without translating the vehicle) is chosen and can follow any feasible spatial trajectory. A connection between configuration flatness and computer vision is used by [Thomas 2014] in the context of MAV grasping and perching maneuvers.
In view of the above, what is needed is the ability to extend the compactness and efficiency advantages of disparity-space obstacle representations to an “egospace” data structure that can accommodate a general range sensor configuration. Further, what is needed is basic obstacle avoidance behavior in egospace coordinates, that may be used with unmanned vehicles (e.g., configuration flat vehicles) as part of a streamlined pipeline for motion planning in unknown, cluttered environments that are referred to herein as “egoplanning”.